package com.leetcode.LeetCode精选TOP面试题;

/**
 * @author 覃国强
 * @date 2022-05-20 18:16
 */
public class 题库_0029_两数相除 {

  public static void main(String[] args) {
    Solution solution = new Solution();
    int divide = solution.divide(1, 1);
    System.out.println(divide);
  }

  static
  class Solution {
    public int divide(int dividend, int divisor) {

      // 负数边界最大，全部转为负数计算，并记录结果符号
      boolean isNegative = false;
      if (dividend > 0) {
        dividend = -dividend;
        isNegative = true;
      }
      if (divisor > 0) {
        divisor = -divisor;
        isNegative = !isNegative;
      }
      // 边界判断
      if(divisor == -1 && dividend == Integer.MIN_VALUE) {
        return isNegative ? Integer.MIN_VALUE : Integer.MAX_VALUE;
      }

      int answer = helper(dividend, divisor);
      return isNegative ? -answer : answer;
    }

    private int helper(int dividend, int divisor) {
      if (divisor == -1) {
        return -dividend;
      }
      // 负数，反着比较
      if (dividend > divisor) {
        return 0;
      }

      int answer = 1;
      int temp = divisor;
      // 加法可能会溢出，转为减法比较
      while (temp > dividend - temp) {
        temp += temp;
        answer += answer;
      }
      return answer + helper(dividend - temp, divisor);
    }
  }

}
